from heapq import heappop,heappush
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
E=[[] for i in range(n+1)]
for i in range(m):
x,y,c=map(int,input().split())
E[x].append((y,c))
E[y].append((x,c))
D=[1<<60]*(n+1)
FR=[-1]*(n+1)
D[1]=0
Q=[(0,1)]
while Q:
dis,x=heappop(Q)
if D[x]!=dis:
continue
for to,cost in E[x]:
if D[to]>dis+cost:
D[to]=dis+cost
heappush(Q,(D[to],to))
FR[to]=x
if FR[n]==-1:
print(-1)
else:
ANS=[n]
while ANS[-1]!=1:
ANS.append(FR[ANS[-1]])
print(*ANS[::-1])
#include<bits/stdc++.h>
using namespace std;
const long long inf=10e+15;
vector<pair<long long int ,long long int >>g[100001];
vector<long long int >dis(100001,inf);
long long int path[100001];
void dijkstra (int source)
{
priority_queue<pair<long long int ,long long int >>q;
q.push({source,0});
dis[source]=0;
while(!q.empty())
{
long long int a=q.top().first;
long long int b=q.top().second;
q.pop();
for(auto x:g[a])
{
long long int u=x.first;
long long int v=x.second;
if(dis[a]+v<dis[u])
{
dis[u]=dis[a]+v;
q.push({u,dis[u]});
path[u]=a;
}
}
}
}
int main()
{
int vertex,edgs;
cin>>vertex>>edgs;
for(int i=1; i<=edgs; i++)
{
int x,y,wt;
cin>>x>>y>>wt;
g[x].push_back({y,wt});
g[y].push_back({x,wt});
}
dijkstra(1);
path[1]=1;
if(path[vertex]==0)
cout<<"-1"<<endl;
else
{
int i=vertex;
vector<int>tmp;
while(i!=1)
{
tmp.push_back(i);
i=path[i];
}
reverse(tmp.begin(),tmp.end());
cout<<"1"<<' ';
for(int i=0; i<tmp.size(); i++)
{
cout<<tmp[i]<<' ';
}
}
}
436. Find Right Interval | 435. Non-overlapping Intervals |
406. Queue Reconstruction by Height | 380. Insert Delete GetRandom O(1) |
332. Reconstruct Itinerary | 368. Largest Divisible Subset |
377. Combination Sum IV | 322. Coin Change |
307. Range Sum Query - Mutable | 287. Find the Duplicate Number |
279. Perfect Squares | 275. H-Index II |
274. H-Index | 260. Single Number III |
240. Search a 2D Matrix II | 238. Product of Array Except Self |
229. Majority Element II | 222. Count Complete Tree Nodes |
215. Kth Largest Element in an Array | 198. House Robber |
153. Find Minimum in Rotated Sorted Array | 150. Evaluate Reverse Polish Notation |
144. Binary Tree Preorder Traversal | 137. Single Number II |
130. Surrounded Regions | 129. Sum Root to Leaf Numbers |
120. Triangle | 102. Binary Tree Level Order Traversal |
96. Unique Binary Search Trees | 75. Sort Colors |